\documentclass[a4paper,10pt]{article}
\usepackage[spanish]{babel}
\usepackage{amsfonts}
\usepackage{algorithm2e}
\usepackage{listings}
\lstset{ %
			language=Python,
			basicstyle=\footnotesize,
			numbers=left,
			stepnumber=1,
			numbersep=4pt,
			tabsize=2,
}

\title{Problema del robo del banco
(Bonnie y Clyde)}
\author{
        Ignacio Garay \\
                \and
        Ariel Liguori\\
        	\and
	Pablo Musumeci
}
\date{\today}

\begin{document}
\maketitle

\begin{abstract}
El presente es un an\'alisis sobre el problema de Bonnie y Clyde y la divisi\'on en partes iguales de un set no homog\'eneo.


\section{Introducci\'on}\label{intro}
El problema del robo del banco o de Bonnie y Clyde permite enfrenta la situaci\'on en la cual se produce el robo de una cantidad $m$ de dinero y quieren dividirlo de la manera m\'as equitativa posible.
Para ello la entrada del algoritmo es la cantidad de items en la bolsa, $n$, y el valor de cada uno $k_i ... k_n$. En el presente an\'alisis se identificar\'an distintos escenarios arbitrarios del problema para los cuales se realizar\'a un an\'alisis de su complejidad algor\'itimica.

\newpage
\section{Planteo}\label{planteo}
El planteo algor\'itmico del problema se basar\'a en cuatro escenarios base a analizar segun lo enunciado a continuaci\'on:

\begin{itemize}
\item \textbf{Escenario A}:
El saco contiene $n$ monedas con 2 denominaciones diferentes: algunas son de $X$ d\'olares, y otras de $Y$ d\'olares. Bonnie y Clyde quieren dividir el bot\'in en partes iguales.\

\item \textbf{Escenario B}:
El saco contiene $n$ monedas, con una cantidad arbitraria de denominaciones distintas, cada denominaci\'on es un entero positivo potencia de 2, Bonnie y Clyde quieren dividir el bot\'in en partes iguales.\
 
\item \textbf{Escenario C}:
El saco contiene $n$ cheques al portador y quieren dividir los cheques de forma tal que cada uno tenga la misma cantidad de dinero.\

\item \textbf{Escenario D}:
El saco contiene $n$ cheques como en el caso (c), pero esta vez Bonnie y Clyde est\'an decididos a aceptar que las partes no sean iguales, permitiendo que la diferencia entre ellas no supere los 100 d\'olares.\

\end{itemize}

\subsection{Escenario A}
Asumimos que hay al menos $a$ monedas de $x$ d\'olares , entonces habr\'a $(n - M)$ monedas de $y$ d\'olares, llamemos $b$ a $(n - m)$.\\
La cantidad total robada ser\'a $T= ax + by$.\\
Por nuestra hip\'otesis queremos determinar si existe una divisi\'on tal que:
\begin{equation}
a_1\x + b_1\y = a_2\x + b_2\y = T/2
\end{equation}.

Debido a que tenemos una cantidad finita de monedas podemos examinar todos los pares $(a_i,b_j)$ en lo cuales $0 \leq a_i \leq a$ y $0 \leq b_j \leq b$.

Esto brindar\'a un orden del tipo $O(ab) = O(n^2)$, lo cual es una soluci\'on por fuerza bruta y, en consecuencia, de \textbf{orden polinomial}.
\\
\newpage
\subsection{Escenario B}
Planteamos para este caso la soluci\'on mediante un algoritmo greedy. 
Primero ordenamos el set de monedas en orden descendente, luego asignamos a Bonnie la moneda con m\'as valor $(a_1)$.
Luego asignamos a Clyde una cantidad similar a la de Bonnie usando las monedas m\'as grandes posibles. 
\begin{equation}
a_2 + ... + a_n = a_1 
\end{equation}

N\'otese que esto siempre puede realizarse ya que el valor de cada moneda puede alcanzarse con monedas de menor denominaci\'on seg\'un lo planteado por la hip\'otesis del escenario.
Finalmente, la cantidad de Clyde igualar\'a la de Bonnie o si ha tomado todas las monedas y a\'un posee menos cantidad que Bonnie significar\'a que no existe una divisi\'on equitativa, esto es:
\begin{equation}
a_2 + ... + a_n < a_1 
\end{equation}

Si se ha logrado una distribuci\'on equitativa tendremos dos escenarios:
\begin{itemize}
\item Se han empleado todas las monedas
\item Se han empleado $j$ monedas, y restan $i = (n - j)$ monedas. Con lo cual procedemos a comenzar nuevamente el algoritmo, dando a Bonnie la moneda de mayor denominaci\'on de las $j$ restantes.
\end{itemize}
   
Dado que cada moneda es asignada una \'unica vez el orden de ello es $O(n)$, luego lo unico que influir\'a en el orden final ser\'a el m\'etodo de ordenamiento adoptado, el cual podra realizarse en orden polinomial. Finalmente este escenario puede ser resuelto en \textbf{tiempo polinomial}.

\newpage
\subsection{Escenario C}
Este caso es NP-Completo, para ello demostraremos que es NP y que es NP-hard, luego por definici\'on diremos que es NP-Completo

\begin{itemize}
\item NP: Dada una bolsa de cheques y una distribuci\'on de los mismos simplemente se procede a la suma de los cheques de Bonnie y los de Clyde y se verifica si la suma es igual. Esto puede realizarse en tiempo polinomial, luego el problema es NP.

\item NP-Hard: Demostraremos que el problema de divisi\'on de cheques de Bonnie y Clyde (Bonnie and Clyde Check Division Problem o BCCD) es NP-hard demostrando que BCCD es una reducci\'on del problema de asignaci\'on de particiones (Set partition problem) y m\'as a\'un que es una reducci\'on del problema de suma de subconjuntos (SubSet-Sum Problem).
\\

El problema de suma de subconjuntos se define como:
\item Dado un set de $X$ enteros y un n\'umero borde o destino $t$, se debe encontrar un subconjunto $Y \subseteq X$ tal que los elementos de $Y$ suman exactamente $t$. Sea $s$ la suma de los elementos de $X$. Agr\'eguese a $X$ un nuevo n\'umero $(s - 2t)$:
\begin{equation}
X^{\prime} = X \cup \{s - 2t\}
\end{equation}
Si existe un subconjunto $Y \subseteq X$ tal que los elementos de $Y$ sumen exactamente $t$, $X^{\prime}$ puede ser dividido en dos partes iguales de tama\~no $(s - t)$.
Si existe un par de  particiones de $X^{\prime}$ en las cuales la suma de sus elementos sea $(s - t)$ y una de las particiones posee el n\'umero $(s - 2t)$ el mismo debera ser eliminado de $X^{\prime}$, luego tenemos subconjunto en el cual la suma de sus elementos es id\'entica a $t$, luego BCCD es NP-Hard.
\\
Demostrado \'esto el problema planteado en \'este escenario es \textbf{NP-Completo}.
\end{itemize}
\\
\newpage
\subsection{Escenario D}
Este caso tambi\'en ser\'a NP-Completo, para demostrarlo nuevamente incurriremos en la doble demostraci\'on de que es NP y NP-Hard.

\begin{itemize}
\item NP: Dada una divisi\'on de cheques a Bonnie y Clyde, $X_b$ y $X_c$, se debe chequear si la diferencia entre ambas es menor a 100 d\'olares.
\begin{equation}
| \sum Xb_i - \sum Xc_i | \leq 100
\end{equation}
Esto es verificable en tiempo polinomial para cada caso, luego es NP.

\item NP-Hard:
Nuevamente para realizar esta prueba partiremos de una reducci\'on, en este caso del Escenario C, el cual demostramos es NP-Completo.
Asumimos que la unidad m\'inima de dinero en un cheque es de un (1) dolar.
En el escenario C determinamos si un set $C = \{C_1,C_2 ...,C_n \} $ puede ser dividido en partes exactamente iguales.
Luego, construimos el nuevo set de cheques del escenario D como:
\begin{equation}
C^\prime = \{C_1 \cdotp 1000 ,C_2 \cdotp 1000 ...,C_n \cdotp 1000 \}
\end{equation}
El set original de cheques $(C)$ podr\'a dividirse exactamente si y solo si $C^\prime$ puede hacerlo aceptando una diferencia menor a 100 d\'olares. 
\end{itemize}



\newpage
\section{Referencias}\label{referencias}
\begin{thebibliography}{9}
\bibitem{KT}
  John Kleinberg and Eva Tardos,
  \emph{Algorithm Design}.
  Addison Wesley, 2006.

\bibitem{CLR}
  Thomas H. Cormen, Charles E. Leiserson, and Ronald L. Rivest.
  \emph{Introduction to Algorithms}.
  The MIT Press, 1990.

\bibitem{GJ}
  M. R. Garey and D. S. Johnson.
  \emph{Computers and Intractability (A Guide to Theory of NP-Completeness)}.
  Freeman, New York, 1979.

\end{thebibliography}
\newpage
\tableofcontents


\end{document}
